package basic.study.leetcode;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName Mid279
 * @Description 完全平方数
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/11 9:27
 * @Version 1.0
 */
public class Mid279 {
    /**
     * DP
     */
    class Solution {
        public int numSquares(int n) {
            int[] dp = new int[n+1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;

            //构建完全平方数组
            int sqrtNum = (int)Math.sqrt(n) + 1;
            int[] sqrtNums = new int[sqrtNum];
            for (int i = 0; i < sqrtNum; i++) {
                sqrtNums[i] = i * i;
            }

            //dp
            for (int i  = 0; i <= n; i++) {
                for (int j = 1; j < sqrtNum; j++) {
                    if (i < sqrtNums[j]) {
                        break;
                    }
                    dp[i] = Math.min(dp[i], dp[i - sqrtNums[j]]+1);
                }
            }
            return dp[n];
        }
    }

    /**
     * 贪心算法
     */
    class Solution1 {
        Set<Integer> square_nums = new HashSet<Integer>();

        public int numSquares(int n) {
            this.square_nums.clear();

            for (int i = 0; i*i <= n; i++) {
                this.square_nums.add(i*i);
            }

            int count = 1;
            for (; count < n; count++) {
                if (is_divided_by(n, count)) {
                    return count;
                }
            }
            return count;
        }

        private boolean is_divided_by(int n, int count) {
            if (count == 1) {
                return square_nums.contains(n);
            }

            for (Integer square: square_nums) {
                if (is_divided_by(n - square, count - 1)) {
                    return true;
                }
            }
            return false;
        }
    }

}
